#include "Sort.h"

void TestInsertSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    InsertSort(a, sizeof(a)/sizeof(a[0]));
    PrintfArray(a, sizeof(a)/sizeof(a[0]));
}


void TestShellSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    ShellSort(a, sizeof(a)/sizeof(a[0]));
    PrintfArray(a, sizeof(a)/sizeof(a[0]));
}

void TestHeapSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    HeapSort(a, sizeof(a)/sizeof(a[0]));
    PrintfArray(a, sizeof(a)/sizeof(a[0]));
}

void TestBubbleSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    BubbleSort(a, sizeof(a)/sizeof(a[0]));
    PrintfArray(a, sizeof(a)/sizeof(a[0]));
}

void TestSelectSort()
{
    //int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    int a[] = {5,2,3,1};
    SelectSort(a, sizeof(a)/sizeof(a[0]));
    PrintfArray(a, sizeof(a)/sizeof(a[0]));
}

void TestQuickSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5, 19, 11, 12, 15, 17, 14, 18, 16, 13, 15 };// (0+9)/2 = 4, a[0]:9,a[4]:7,a[9]:5
    //printf("%d\n", a[GetMidIndex(a, 0, sizeof(a)/sizeof(a[0])-1)]);//测试三数取中
    QuickSort(a, 0, sizeof(a)/sizeof(a[0])-1);
    PrintfArray(a, sizeof(a)/sizeof(a[0]));
}

void TestQuickSortNonR()
{
    //int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    //int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5, 19, 11, 12, 15, 17, 14, 18, 16, 13, 15 };
//    QuickSortNonR(a, 0, sizeof(a)/sizeof(a[0])-1);
//    PrintfArray(a, sizeof(a)/sizeof(a[0]));
    srand(time(0));
    const int N = 100;
    int* a = (int*)malloc(sizeof(int)*N);
    for (int i = 0; i < N; ++i)
    {
        a[i] = rand()%100;
    }
    QuickSortNonR(a, 0, N-1);
    PrintfArray(a, N);
    free(a);
}

void TestMergeSort()
{
    //int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    int a[] = {3, -1};
    MergeSort(a, sizeof(a)/sizeof(a[0]));
    PrintfArray(a, sizeof(a)/sizeof(a[0]));

    /*
    srand(time(0));
    const int N = 100;
    int* a1 = (int*)malloc(sizeof(int)*N);
    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand()%100;
    }
    MergeSort(a1, N);
    PrintfArray(a1, N);
    free(a1);
     */
}

void TestMergeSortNonR()
{
    //int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5, -3, -5 };
    int a[] = {3, -1};
    MergeSortNonR(a, sizeof(a)/sizeof(a[0]));
    PrintfArray(a, sizeof(a)/sizeof(a[0]));
    /*
    srand(time(0));
    const int N = 100;
    int* a1 = (int*)malloc(sizeof(int)*N);
    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand()%100;
    }
    MergeSortNonR(a1, N);
    PrintfArray(a1, N);
    free(a1);
     */
}

void TestSortTop()
{
    srand(time(0));
    const int N = 1000000;
    int* a1 = (int*)malloc(sizeof(int)*N);
    int* a2 = (int*)malloc(sizeof(int)*N);
    int* a3 = (int*)malloc(sizeof(int)*N);
    int* a4 = (int*)malloc(sizeof(int)*N);
    int* a5 = (int*)malloc(sizeof(int)*N);
    int* a6 = (int*)malloc(sizeof(int)*N);
    int* a7 = (int*)malloc(sizeof(int)*N);
    int* a8 = (int*)malloc(sizeof(int)*N);
    int* a9 = (int*)malloc(sizeof(int)*N);

    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
        a8[i] = a1[i];
        a9[i] = a1[i];
    }
    int begin1 = clock();
    //InsertSort(a1, N);
    int end1 = clock();

    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();

    int begin3 = clock();
    //SelectSort(a3, N);
    int end3 = clock();

    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();

    int begin5 = clock();
    QuickSort(a5, 0, N-1);
    int end5 = clock();

    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();

    int begin7 = clock();
    //BubbleSort(a7, N);
    int end7 = clock();

    int begin8 = clock();
    QuickSortNonR(a8, 0, N-1);
    int end8 = clock();

    int begin9 = clock();
    MergeSortNonR(a9, N);
    int end9 = clock();

    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - begin6);
    printf("BubbleSort:%d\n", end7 - begin7);
    printf("QuickSortNonR:%d\n", end8 - begin8);
    printf("MergeSortNonR:%d\n", end9 - begin9);
    printf("callCount:%d\n", callCount);

    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
    free(a7);
    free(a8);
}

int main()
{
//    TestInsertSort();
//    TestShellSort();
//    TestHeapSort();
//    TestBubbleSort();
//    TestSelectSort();
//   TestQuickSort();
//     TestQuickSortNonR();
//  TestMergeSort();
//    TestMergeSortNonR();
   TestSortTop();

}
